import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-09-12
 * Time: 14:38
 */
public class TestCode8 {
        //题目是小于n的最大数所以不能等于n，如果要等于n，那么去掉这个getMax的部分即可
        //check是用来判断长度是否能和n一样的，这里minValue就是nums[0]
        static boolean check(String str, int minValue) {
            char c = str.charAt(0);
            if (minValue < c - '0') {
                return true;
            } else if (minValue == c - '0') {
                // 该位置相同,则递归往下查找
                return check(str.substring(1), minValue);
            } else {
                return false;
            }
        }

        //得到用nums中的数字能够拼出的数字的上限
        static int getMax(int[] nums, int n) {
            // 把n转成字符串,方便后面操作
            String s = String.valueOf(n);
            if (check(s, nums[0])) {
                // 长度可以和n一样
                return n - 1;
            } else {
                // 如果位数小1的话,那就直接都取nums数组中最大的那个元素拼接就行,只要位数-1
                return (int) Math.pow(10, s.length() - 1) - 1;
            }
        }

        // 二分查找，找到 <= target 的最大索引
        public static int binarySearch(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] <= target) l = mid + 1;
                else r = mid - 1;
            }
            return r; // r 是 <= target 的最大索引
        }

        // 返回 nums 中比 str[u] 小的最大索引
        public static int getIndex(int[] nums, String str, int u) {
            int cur = str.charAt(u) - '0';
            int index = binarySearch(nums, cur);
            // 如果当前位不能取 cur，选更小的
            while (index >= 0 && nums[index] > cur) index--;
            return index;
        }

        public static String getMaxBelowN(int[] nums, int n) {
            Arrays.sort(nums);
            int maxValue = getMax(nums,n);
            String s = String.valueOf(maxValue);
            StringBuilder res = new StringBuilder();
            boolean flag = false;

            for (int i = 0; i < s.length(); i++) {
                int index = getIndex(nums, s, i);
                if (index == -1) {  // 如果无法选择当前位，就回退
                    while (res.length() > 0) {
                        int lastIndex = res.length() - 1;
                        int lastDigit = res.charAt(lastIndex) - '0';

                        int newIndex = binarySearch(nums, lastDigit) - 1;
                        if (newIndex >= 0) {
                            res.setCharAt(lastIndex, (char) ('0' + nums[newIndex]));
                            break;
                        }
                        res.deleteCharAt(lastIndex);
                    }

                    // 全部删除，返回最大可选数
                    if (res.length() == 0) {
                        char[] maxNum = new char[s.length() - 1];
                        Arrays.fill(maxNum, (char) ('0' + nums[nums.length - 1]));
                        return new String(maxNum);
                    }

                    while (res.length() < s.length()) {
                        res.append(nums[nums.length - 1]);
                    }

                    return res.toString();
                }

                res.append(nums[index]);
                if (nums[index] < s.charAt(i) - '0') flag = true;
            }

            return res.toString();
        }

        public static void main(String[] args) {
            int[] num;
            int n;

            num = new int[]{1, 2, 4, 6, 8};
            n = 2411;
            System.out.println(getMaxBelowN(num, n));  // 2288
            num = new int[]{4, 5, 6};
            n = 23;
            System.out.println(getMaxBelowN(num, n));  // 6
        }
}
